#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define int long long
int INF = 0x3f3f3f3f3f3f3f3f;



//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	solve();
//	return 0;
//}

//int f[305][305];
//int n, m, p;
//int q[200005], a[200005], b[200005];
//
//struct edge
//{
//	int u, v, val;
//}ge[90000];
//
//void floyd() {
//	for (int k = 1; k <= n; k++) {
//		for (int i = 1; i <= n; i++) {
//			for (int j = 1; j <= n; j++) {
//				if (f[i][j] > f[i][k] + f[k][j]) {
//					f[i][j] = f[i][k] + f[k][j];
//				}
//			}
//		}
//	}
//}
//
//void up(int x) {
//	int u = ge[x].u, v = ge[x].v, w = ge[x].val;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++) {
//			f[i][j] = min({ f[i][j],f[i][u] + w + f[v][j],f[i][v] + w + f[u][j] });
//		}
//	}
//}
//
//void solve() {
//	cin >> n >> m >> p;
//	memset(f, INF, sizeof(f));
//	for (int i = 1; i <= n; i++)f[i][i] = 0;
//	for (int i = 1, u, v, w; i <= m; i++) {
//		cin >> u >> v >> w;
//		f[v][u] = f[u][v] = min(f[u][v], w);
//		ge[i] = { u,v ,w };
//	}
//	for (int i = 1; i <= p; i++) {
//		cin >> q[i];
//		if (q[i] == 1) {
//			cin >> a[i];
//			int u = ge[a[i]].u, v = ge[a[i]].v;
//			f[v][u] = f[u][v] = INF;
//		}
//		else cin >> a[i] >> b[i];
//	}
//	floyd();
//	vector<int> ans;
//	for (int i = p; i >= 1; i--) {
//		if (q[i] == 2) {
//			int tmp = f[a[i]][b[i]] == INF ? -1 : f[a[i]][b[i]];
//			ans.push_back(tmp);
//		}
//		else {
//			up(a[i]);
//		}
//	}
//	for (int i = ans.size() - 1; i >= 0; i--) {
//		cout << ans[i] << '\n';
//	}
//}

//int a[200005];
//int n;
//int dp[200005];
//int ans;
//
//void solve() {
//	cin >> n;
//
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//
//	}
//	for (int i = 1; i <= n; i++) {
//		dp[i]
//	}
//
//
//
//
//}

//int n, m;
//int x[200005], a[200005];
//
//void solve() {
//	cin >> n >> m;
//	map<int, int> mp;
//	int tot = 0;
//	for (int i = 1; i <= m; i++) {
//		cin >> x[i];
//	}
//	for (int i = 1; i <= m; i++) {
//		cin >> a[i];
//		tot += a[i];
//		mp[x[i]] = a[i];
//	}
//	sort(x + 1, x + 1 + m);
//	if (tot != n) {
//		cout << -1 << '\n';
//		return;
//	}
//	int ans = 0;
//	int cur = 1;
//	mp[n] = 0;
//	x[m + 1] = n;
//	while (cur < n) {
//		int r = lower_bound(x + 1, x + 1 + m, cur + 1) - x;
//		int len = x[r] - cur - 1, tmp = mp[cur] - len - 1;
//		if (tmp < 0) {
//			cout << -1 << '\n';
//			return;
//		}
//		ans += len * (len + 1) / 2;
//		ans += tmp * (len + 1);
//		mp[x[r]] += tmp;
//		cur = x[r];
//	}
//	cout << ans << '\n';
//}

//int x[200005];
//int w[200005];
//int s[800005];
//int n;
//
//void up(int p) {
//	s[p] = s[2 * p] + s[2 * p + 1];
//}
//
//void build(int l, int r, int p) {
//	if (l == r) {
//		s[p] = w[l];
//		return;
//	}
//	int m = (l + r) >> 1;
//	build(l, m, 2 * p);
//	build(m + 1, r, 2 * p + 1);
//	up(p);
//}
//
//int quer(int jl, int jr, int l, int r, int p) {
//	if (jl <= l && jr >= r) {
//		return s[p];
//	}
//	int m = (l + r) >> 1;
//	int ans = 0;
//	if (jl <= m)
//		ans += quer(jl, jr, l, m, 2 * p);
//	if (jr > m)
//		ans += quer(jl, jr, m + 1, r, 2 * p + 1);
//	return ans;
//}
//
//void solve() {
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> x[i];
//	}
//	for (int i = 1; i <= n; i++) {
//		cin >> w[i];
//	}
//	build(1, n, 1);
//	int q;
//	cin >> q;
//	while (q--) {
//		int l, r;
//		cin >> l >> r;
//		int ll = lower_bound(x + 1, x + 1 + n, l) - x;
//		int rr = upper_bound(x + 1, x + 1 + n, r) - x - 1;
//		if ((ll < 1 && rr < 1) || (ll > n && rr > n)) {
//			cout << 0 << '\n';
//			continue;
//		}
//		if (ll < 1) ll = 1;
//		if (rr < 1) rr = 1;
//		if (ll > n) ll = n;
//		if (rr > n) rr = n;
//		cout << quer(ll, rr, 1, n, 1) << '\n';
//	}
//}


//int n, q;
//int lcur = 1, rcur = 2;
//
//bool rcheck(int s, int t) {
//	if (t > s) {
//		if (lcur > s && lcur < t)
//			return true;
//	}
//	else {
//		if (lcur > s || lcur < t)
//			return true;
//	}
//	return false;
//}
//bool lcheck(int s, int t) {
//	if (t > s) {
//		if (rcur > s && rcur < t)
//			return true;
//	}
//	else {
//		if (rcur > s || rcur < t)
//			return true;
//	}
//	return false;
//}
//
//void solve() {
//	cin >> n >> q;
//
//	int ans = 0;
//	for (int i = 1; i <= q; i++) {
//		char ha;
//		int t;
//		cin >> ha >> t;
//		if (ha == 'R') {
//			int tmp = (t - rcur + n) % n;
//			if (rcheck(rcur, t)) {
//				tmp = (rcur - t + n) % n;
//			}
//			ans += tmp;
//			rcur = t;
//		}
//		else {
//			int tmp = (t - lcur + n) % n;
//			if (lcheck(lcur, t)) {
//				tmp = (lcur - t + n) % n;
//			}
//			ans += tmp;
//			lcur = t;
//		}
//	}
//	cout << ans << '\n';
//}
